package _09_heap;

import java.util.StringJoiner;

/**
 * @author: mornd
 * @dateTime: 2023/6/10 - 22:02
 * 小顶堆
 */
public class IntMinHeap  {
    int[] data;
    int size;

    public IntMinHeap(int c) {
        data = new int[c];
    }

    public IntMinHeap(int[] arr) {
        data = arr;
        size = data.length;
        heapify();
    }

    /**
     * 建堆
     * 分成两步：
     * 1、找到最后一个非叶子节点
     * 2、从后至前，对每个节点进行下潜
     */
    private void heapify() {
        /*
            找到最后一个非叶子节点的下标（下标0代表root的话），套用公式：size >> 1 - 1
         */
        int minFullParent = (size >>> 1) - 1;
        for (int i = minFullParent; i >= 0; i--) {
            down(i);
        }
    }

    /**
     * 下潜节点，如果父节点有子节点的话，就将最大的子节点替换掉父节点
     *
     * @param parent 父节点下标
     */
    public void down(int parent) {
        // 求出左子节点下标
        int left = (parent << 1) + 1;
        // 求出右子节点下标
        int right = left + 1;
        // 假设父节点最大
        int max = parent;
        if (left < size && data[left] < data[max]) {
            // 左子节点大
            max = left;
        }
        if (right < size && data[right] < data[max]) {
            // 右子节点大
            max = right;
        }
        if (max != parent) {
            // 交换
            swap(parent, max);
            // 递归
            down(max);
        }
    }

    private void swap(int i, int j) {
        int t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    // 弹出根节点，并对堆进行比对
    public int poll() {
        return poll(0);
    }

    public int poll(int index) {
        if (isEmpty() || index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int i = data[index];

        if (index != --size) {
            swap(index, size);
            down(index);
        }
        return i;
    }

    private void grow() {
        // 扩容
        int[] newArr = new int[data.length + (data.length >>> 1)];
        System.arraycopy(data, 0, newArr, 0, size);
        data = newArr;
    }

    public boolean offer(int i) {
        if (isFull()) {
            grow();
        }
        data[size] = i;
        up(size);
        size++;
        return true;
    }

    /**
     * 上浮
     *
     * @param i
     */
    public void up(int i) {
        if (i <= 0) {
            return;
        }

        // 求出父节点
        int parent = (i - 1) / 2;
        if (data[i] < data[parent]) {
            swap(i, parent);
            up(parent);
        }
    }

    /**
     * 替换堆顶元素
     *
     * @param replaced
     */
    public void replace(int replaced) {
        data[0] = replaced;
        down(0);
    }

    public int peek() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        return data[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == data.length;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringJoiner joiner = new StringJoiner(", ", "[", "]");
        for (int i = 0; i < size; i++) {
            joiner.add(String.valueOf(data[i]));
        }
        return joiner.toString();
    }
}
